package leetcode.code0901;

//执行用时：60 ms, 在所有 Java 提交中击败了22.36%的用户
//
//内存消耗：50.6 MB, 在所有 Java 提交中击败了8.30%的用户
//
//通过测试用例：99 / 99
public class StockSpanner3 {

	int[][] stack;
	int p;
	int id;

	public StockSpanner3() {
		stack = new int[10000][2];
		p = 0;
		id = 0;
	}

	public int next(int price) {
		while (p != 0 && price >= stack[p - 1][1]) {
			p--;
		}
		int ans = p == 0 ? id + 1 : id - stack[p - 1][0];
		stack[p++] = new int[] { id++, price };
		return ans;
	}

	public static void main(String[] args) {
		StockSpanner3 S = new StockSpanner3();
		S.next(100);
		S.next(80);
		S.next(60);
		S.next(70);
		S.next(60);
		S.next(75);
		S.next(85);

	}

}
